//输入一个字符串，打印出该字符串中字符的所有排列。 
//
// 
//
// 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 
//
// 
//
// 示例: 
//
// 输入：s = "abc"
//输出：["abc","acb","bac","bca","cab","cba"]
// 
//
// 
//
// 限制： 
//
// 1 <= s 的长度 <= 8 
// Related Topics 字符串 回溯 👍 571 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer38 {
    boolean[] used ;
    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public String[] permutation(String s) {
//        if(s.length() < 2) return new String[];
        used = new boolean[s.length()];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        traversal(arr,0);
        String[] strings = result.toArray(new String[result.size()]);
        return strings;
    }

    public void traversal(char[] arr, int index){
        if(sb.length() == arr.length){
            result.add(new String(sb));
            return;
        }
        for(int i = 0; i < arr.length; i++){
            if(used[i]) continue;
            if(i > 0 && arr[i] == arr[i-1] && !used[i-1]) continue;
            sb.append(arr[i]);
            used[i] = true;
            traversal(arr, index+1);
            sb.deleteCharAt(sb.length()-1);
            used[i] = false;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
